42. Trapping Rain Water

Question

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining

Example 1

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Solution 1: Brute Force (TLE)

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        ans = 0
        for i in range(1, n-1):
            lftMax = rhtMax = height[i]
            for j in range(i):
                lftMax = max(lftMax, height[j])
            for j in range(i+1, n):
                rhtMax = max(rhtMax, height[j])
                
            ans += min(lftMax, rhtMax) - height[i]
        return ans

Time Complexity: O(N^2)
Space Complexity: O(1)

Solution 2: Stack

Time Complexity: O(N)
Space Complexity: O(N)

Solution 3: Horizon Scan

Solution 4: Two Pointer

Time Complexity: O(N)
Space Complexity: O(1)

Reference

https://www.geeksforgeeks.org/trapping-rain-water/
https://leetcode.com/problems/trapping-rain-water/discuss/2610031/Python-Two-Pointers-O(N)-Time-O(1)-Space

Follow-up: Trapping Rain Water II

TODO

Time Complexity: O()
Space Complexity: O()